package com.zjj.lbw.algorithm.sort;

import java.util.Arrays;

/**
 * @author zhanglei.zjj
 * @description 计数排序
 * @date 2023/3/26 14:43
 */
public class CountingSort {
    public static void main(String[] args) {
        int[] unsortedArr = new int[]{2, 5, 3, 0, 2, 3, 0, 3};
//        int[] unsortedArr = new int[]{4, 2, 5, 3, 7, 10, 4, 5};
        countSort(unsortedArr);
    }
    
    static void countSort(int[] arr) {
        System.out.println("排序前元素顺序：" + Arrays.toString(arr));

        // 确定原始数组的最大值、最小值
        int min = arr[0];
        int max = arr[0];
        for (int item : arr) {
            if (item < min) {
                min = item;
            }
            if (item > max) {
                max = item;
            }
        }

        // 确定计数数组容量
        int interval = min;
        int[] countArr = new int[max - min + 1];

        // 原始数组进行计数统计
        for (int i = 0; i < arr.length; i++) {
            countArr[arr[i] - interval] ++;
        }
        System.out.println("统计后的计数数组为：" + Arrays.toString(countArr));

        // 根据计数数组排序
        int originArrIndex = 0;
        for (int i = 0; i < countArr.length; i++) {
            while (countArr [i] > 0) {
                arr[originArrIndex] = i + interval;
                originArrIndex ++;
                countArr[i] --;
            }
        }

        System.out.println("排序后元素顺序为：" + Arrays.toString(arr));
    }
}
